
class SingleLinkNode:
    def __init__(self,item=None):
        self.item = item
        self.next = None

    def __repr__(self):
        return str(self.item)

class SingleLinkList:

    def __init__(self):
        self.head = None
        self.tail = None

    def append(self,item):
        node = SingleLinkNode(item)
        if self.head is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        return self

    def iternodes(self):
        current = self.head
        while current:
            yield current
            current = current.next

# l1 = SingleLinkList()
#
# l1.append(1).append(2).append(3)
# print(l1.head)
# print(l1.tail)
# for i,item in enumerate(l1.iternodes()):
#     print(i,item)

class DoubleLinkNode:
    def __init__(self,item):
        self.item = item
        self.prev = None
        self.next = None

    def __repr__(self):
        return "[item:{}\tprev:{}\tnext:{}]".format(
            self.item,
            self.prev.item if self.prev else None,
            self.next.item if self.next else None
        )
    __str__ = __repr__

class DoubleLinklist:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def __getitem__(self, index):
        #out of range
        if index >= len(self) or index < -len(self):
            raise IndexError("Index out of range:{}".format(index))
        reverse = False if index >= 0 else True
        start = 0 if index >= 0 else 1
        for i,node in enumerate(self.iternodes(reverse),start):
            if abs(index) == i:
                return node

    def __reversed__(self):
        return self.iternodes(True)

    def __setitem__(self, index, value):
        self[index].item = value
    def append(self,item):
        node = DoubleLinkNode(item)
        if self.head is None:
            self.head = node
        else:
            self.tail.next = node
            self.tail.next.prev = self.tail
        self.tail = node
        self._size += 1
        return self

    def pop(self):
        if self.tail is None:
            raise Exception("list is Empty")
        popnode:DoubleLinkNode = self.tail
        #Just one node
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
        #more than one node
            self.tail = popnode.prev
            popnode.prev.next = None
        self._size -= 1
        return popnode.item

    def iternodes(self,reverse=False):
        # if reverse == False:
        #     current:DoubleLinkNode = self.head
        #     while current:
        #         yield current
        #         current = current.next
        # else:
        #     current:DoubleLinkNode = self.tail
        #     while current:
        #         yield  current
        #         current = current.prev
        current:DoubleLinkNode = self.head if reverse == False else self.tail
        while current:
            yield current
            current = current.next if reverse == False else current.prev

    __iter__ = iternodes

    def insert(self,index,item):
        # if index < 0:
        #     raise Exception("not index:{}".format(index))
        # oldNode = None
        # for i,node in enumerate(self.iternodes(False)):
        #     if index == i:
        #         oldNode = node
        #         break
        # #tail insert
        # else:
        #     self.append(item)
        #     return
        if index >= len(self):
            self.append(item)
            return
        if index < -len(self):
            index = 0
        oldNode = self[index]

        newNode = DoubleLinkNode(item)
        #head insert
        if index == 0:
            self.head = newNode

        #midpiece insert
        else:
            newNode.prev = oldNode.prev
            oldNode.prev.next = newNode
        newNode.next = oldNode
        oldNode.prev = newNode
        self._size += 1

    def remove(self,index):
        if self.tail is None:
            raise  Exception('list Empty')
        # if index < 0:
        #     raise Exception("not index:{}".format(index))
        #
        # removenode = None
        # for i,node in enumerate(self.iternodes(False)):
        #     if index == i:
        #         removenode = node
        #         break
        # else:
        #     raise Exception("index out of range:{}".format(index))
        removenode = self[index]
        #remove head
        if index == 0 and self.head is not self.tail:
            self.head = removenode.next
            removenode.next.prev = None

        #remove midpiece
        elif removenode.prev is not None and removenode.next is not None:
            removenode.next.prev = removenode.prev
            removenode.prev.next = removenode.next

        #remove tail
        elif removenode.next is None and removenode.prev is not None:
            self.tail = removenode.prev
            removenode.prev.next = None

        #only one node
        else:
            self.head = None
            self.tail = None

        del removenode
        self._size -= 1

ll = DoubleLinklist()
ll.append(1).append(2).append(3)
ll.append('abc').append('def')
print(ll.head)
print(ll.tail)
print("___________")
for i, item in enumerate(ll.iternodes()):
    print(i,item)

ll.insert(0,'start')
ll.insert(20,'end')
print("++++++++++++")
for i, item in enumerate(ll.iternodes()):
    print(i,item)
ll.insert(4,'4')
print("------------")
for i, item in enumerate(ll.iternodes()):
    print(i,item)
print("************")
ll.remove(5)
ll.remove(4)
ll.remove(0)
ll.pop()
ll.remove(3)
for i, item in enumerate(ll.iternodes()):
    print(i,item)

ll[0] = 100
ll[-1] = 300
print('^^^^^^^^^^^^^^')
print(*reversed(ll),sep='\n')






